#ifndef BITMAP_H_
#define BITMAP_H_

#include <cstddef>
#include <cstdint>
#include <memory>
#include <string>
#include <utility>


namespace lxj
{
inline std::string getNumBinary(char a)
{
    std::string binary;
    binary.reserve(32);
    for (int i = 7; i >= 0; i--) {
        char c = ((a & (1 << i)) != 0) ? '1' : '0';
        binary.push_back(c);
    }
    return binary;
}

class Bitmap {
    std::unique_ptr<char[]> m_begin;
    size_t                  m_size;

public:
    Bitmap(size_t n)
        : m_begin(std::move(std::make_unique<char[]>((n + 4 - 1) / 4))), m_size((n + 4 - 1) / 4 * 8)
    {
        for (size_t i = 0; i < m_size / 8; i++) {
            m_begin[i] = 0b00000000;
        }
    }
    Bitmap(const Bitmap&) = delete;
    Bitmap(Bitmap&& other) : m_begin(std::move(other.m_begin)), m_size(other.m_size) {}

    inline void add(int num)
    {
        size_t  center = (m_size - 1) / 2;
        int64_t border = center + num;
        if (border < 0 || border >= m_size) {
            size_t n = num >= 0 ? num : -num + 1;
            reserve(n);
            center = (m_size - 1) / 2;
        }
        size_t index = center + num;
        m_begin[index / 8] |= 0b00000001 << (7 - index % 8);
    }

    inline void remove(int num)
    {
        size_t  center = (m_size - 1) / 2;
        int64_t border = center + num;
        if (border < 0 || border >= m_size) return;
        size_t index = center + num;
        m_begin[index / 8] &= ~(0b00000001 << (7 - index % 8));
    }

    // 改变num位置的状态
    inline void reverse(int num)
    {
        size_t  center = (m_size - 1) / 2;
        int64_t border = center + num;
        if (border < 0 || border >= m_size) return;
        size_t index = center + num;
        m_begin[index / 8] ^= 0b00000001 << (7 - index % 8);
    }

    inline void reserve(size_t num)
    {
        size_t  center = (m_size - 1) / 2;
        int64_t border = center + num;
        if (border >= 0 && border < m_size) return;
        auto p = std::make_unique<char[]>((num + 4 - 1) / 4);
        m_begin.swap(p);
        m_size = (num + 4 - 1) / 4 * 8;
    }

    inline bool contains(int num) const
    {
        size_t  center = (m_size - 1) / 2;
        int64_t border = center + num;
        if (border < 0 || border >= m_size) return false;
        size_t index = center + num;
        return (0b00000001 << (7 - index % 8) & m_begin[index / 8]) != 0;
    }

    // 统计1的数量
    inline int count()
    {
        int ans = 0;
        for (size_t i = 0; i < m_size / 8; i++) {
            int  sum = 0;
            char c   = m_begin[i];
            while (c != 0b00000000) {
                c -= c & (-c);
                sum++;
            }
            ans += sum;
        }
        return ans;
    }

    std::string str()
    {
        std::string binary;
        binary.reserve(m_size + m_size / 8);
        for (int i = 0; i < m_size / 8; i++) {
            for (int k = 7; k >= 0; k--) {
                char c = ((m_begin[i] & (1 << k)) != 0) ? '1' : '0';
                binary.push_back(c);
            }
            binary.push_back(',');
        }
        return binary;
    }
};
}   // namespace lxj

#endif